package com.lanluo.service.lookup;

import java.util.Arrays;

public class BinarySearch {

    /**
     * 二分查找(从有序数组中查找关键字所在的位置)
     * @param key 查找的关键字
     * @param a   数组
     * @return
     *
     * 1. 定义开始位置start = 0 , 结束位置end = a.length-1
     * 2. 中间位置 min = start + (end-start)/2
     * 3. if key<a[min] end=min-1   if key>a[min] start=min+1   else min
     * 4. while start<=end 循环第二步第三步
     *
     */
    public static int rank(int key, int[] a) {
        int start = 0;
        int end = a.length-1;
        while (start <= end) {
            int mid = start + (end-start) / 2;
            if(key < a[mid]) end = mid-1;
            else if(key > a[mid]) start = mid+1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5 };
        int key =4;
        Arrays.sort(a);
        System.out.println(a.toString());
        System.out.println(rank(key, a));
    }
}
